/**
 * 返回路径总和
 * @param m 行数
 * @param n 列数
 * @returns 路径总和
 */
export function uniquePaths (m: number, n: number): number {
    const pathCount = new PathCount(m, n);
    return pathCount.getPathCount(m, n);
}

class PathCount {
    private pathCounts: number[][];

    /**
     * @param m 行数 
     * @param n 列数
     */
    constructor(m: number, n: number) {
        this.pathCounts = new Array(m);
        // 初始化
        let i = 0;
        while (i < m) {
            this.pathCounts[i] = new Array(n);
            i++;
        }

        // 第1行和第1列初始化为1
        for (let j = 0; j < this.pathCounts[0].length; j++) {
            this.pathCounts[0][j] = 1;
        }
        for (let j = 1; j < this.pathCounts.length; j++) {
            this.pathCounts[j][0] = 1;
        }

        this.calPathCount(m, n);
    }

    private calPathCount (m: number, n: number) {
        for (let i = 1; i < m; i++) {
            for (let j = 1; j < n; j++) {
                this.pathCounts[i][j] = this.pathCounts[i-1][j] + this.pathCounts[i][j-1];
            }
        }
    }

    public getPathCount (m: number, n: number) {
        return this.pathCounts[m-1][n-1];
    }
}